home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3396 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.1 KB
  1. Path: gryphon.phoenix.net!usenet
  2. From: brucew@phoenix.net (Bruce Wedding)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finding a prime number
  5. Date: Sun, 28 Jan 1996 18:49:55 GMT
  6. Organization: BranPaul Systems
  7. Message-ID: <4ege88$8mi@gryphon.phoenix.net>
  8. References: <4e875s$nqk@reader2.ix.netcom.com> <4e8pds$4va@nw002.infi.net>
  9. NNTP-Posting-Host: dial77.phoenix.net
  10. X-Newsreader: Moe's Newsreader    
  11.  
  12. nngis@norfolk.infi.net (Greg DiGiorgio) wrote:
  13.  
  14.  
  15. >#include <stdio.h>
  16.  
  17. >int is_prime(int n) {    /* Is it a prime number... */
  18.  
  19. >    int i;    /* Loop counter */
  20. >    for (i=2; i<n; i++) {
  21. You are wasting a lot of time here.  There are two easy things
  22. you can do to speed this up.  1.  Increment i by two so as to
  23. only check odd numbers.  You will of course, have to make 
  24. some other changes for this to work.  2.  Only check up
  25. to the sqrt(n).  Anything past that is redundant.  Calculate
  26. the square root first, do not place it in the loop.
  27.  
  28.  
  29. Bruce D. Wedding                        Have Compiler, Will Travel!
  30.               Perspicacious Programming Performed Promptly
  31. Katy, Texas, USA, Planet Earth, Milkyway Galaxy, Known Universe
  32.  
  33.